import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 首先把字典中的单词放在哈希表中，方便后续O(1)时间查找
        // 创建一个哈希表
        Set<String> wordListHashSet = new HashSet<>();
        // 遍历数组 放入哈希表
        for (String s : wordList) {
            wordListHashSet.add(s);
        }
        // 还需要再设置一个哈希表 用于标记已经搜索过的单词
        Set<String> visHashSet = new HashSet<>();
        // 处理边界条件
        if (!wordListHashSet.contains(endWord)) {
            return 0;
        }
        // 创建一个队列 将每一层的加入队列
        Queue<String> q = new LinkedList<>();
        // 将 beginWord 加入到队列
        q.offer(beginWord);
        // 定义一个变量，统计结果
        int ret = 1;
        while (!q.isEmpty()) {
            ret++;
            // 计算队列的大小
            int sz = q.size();
            while (sz-- != 0) {
                // 取出队头元素
                String t = q.poll();
                for (int i = 0; i < t.length(); i++) {
                    // 将队头元素转换为数组
                    char[] tmp = t.toCharArray();
                    // 将元素进行替换
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        tmp[i] = ch;
                        // 转换成string
                        String next = new String(tmp);
                        // 进行判断
                        if (wordListHashSet.contains(next) && !visHashSet.contains(next)) {
                            if (next.equals(endWord)) {
                                return ret;
                            }
                            q.offer(next);
                            visHashSet.add(next);
                        }
                    }
                }
            }
        }
        return 0;
    }
}